package tree;

/**
 * @author : Rookie
 * @description : 二叉搜索树转化为累加树
 * @date : 2023/11/5
 */
public class BinarySearchTreeToCumulativeTree {
    /**
     * 记录前面节点的累加值
     */
    private static int prev = 0;

    public static void main(String[] args) {
        int[] tree = new int[] {4,1,6,0,2,5,7,-1,-1,-1,3,-1,-1,-1,8};
        TreeNode root = BinaryTreeUtil.buildTree(tree);
        TreeNode treeNode = covertCumulativeTree(root);
        BinaryTreeUtil.Traversal.sequenceTraversal(treeNode);
    }

    private static TreeNode covertCumulativeTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        // 右
        root.right = covertCumulativeTree(root.right);
        // 中
        root.element += prev;
        prev = root.element;
        // 左
        root.left = covertCumulativeTree(root.left);
        return root;
    }
}
